﻿using System;
using System.Net;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Documents;
using System.Windows.Ink;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Animation;
using System.Windows.Shapes;
using System.Collections.Generic;

namespace ZombieMonkeys.Vibria.Logic
{
    public class PuzzleSolver
    {
        //This is what everything is about, the puzzle array of squares to solve
        public Square[,] squareArray;

        private bool hintMode;

        //these variables will be used by the recursive brute force algorithm
        private bool BruteForceStop = false;
        private Stack<int> ActualStack = new Stack<int>();
        private Stack<string> PossibleStack = new Stack<string>();

        public PuzzleSolver(List<Square> puzzletoSolve)
        {
            int side = (int)Math.Sqrt(puzzletoSolve.Count);
            squareArray = new Square[side, side];
            //populate an array with squares for easier indexing by the solver
            //Some of the algorithms might be easier to work with an array
            for (int i = 0; i < puzzletoSolve.Count; i++)
            {
                //using the row and column identifiers from the actual squares to make sure they go to the right place
                //just in case they are out of order for some reason
                int row = puzzletoSolve[i].GetRow();
                int col = puzzletoSolve[i].GetColumn();
                squareArray[row, col] = puzzletoSolve[i];
            }
        }

        /// <summary>
        /// Returns the current list of squares in use by the PuzzleSolver
        /// </summary>
        /// <returns></returns>
        public List<Square> ReturnSquares()
        { 
            List<Square> squareList = new List<Square>();

            for (int r = 0; r < squareArray.GetLength(0); r++)
			{
                for (int c = 0; c < squareArray.GetLength(1); c++)
                {
                    squareList.Add(squareArray[r,c]);
                }
			}
            return squareList;
        }

        /// <summary>
        /// Get Set for hint mode
        /// </summary>
        public bool HintMode
        {
            get
            {
                return hintMode;
            }
            set
            {
                hintMode = value;
            }
        }

        /// <summary>
        /// Used to determine valid possible values for an empty square
        /// </summary>
        /// <param name="row">row identifier for square</param>
        /// <param name="col">column identifier for square</param>
        /// <returns>string of possible values</returns>
        public string CalculatePossibleValues(int row, int col)
        {
            //just checking to make sure the square is empty
            if (squareArray[row, col].GetValue() != "0")
            {
                return string.Empty;
            }
            string str = "123456789";
            //use the following for minigrid
            int rr = row / 3;
            int cc = col / 3;
            //look at the column to remove values that are already used
            for (int i = 0; i < 9; i++)
            {
                str = str.Replace(squareArray[i, col].GetValue(), string.Empty);
            }
            //look at the row to remove values that are already used
            for (int i = 0; i < 9; i++)
            {
                str = str.Replace(squareArray[row, i].GetValue(), string.Empty);
            }
            //look at the minigrids to remove values that are already used

            for (int i = (3 * rr); i < (3 * rr) + 3; i++)
            {
                for (int j = (3 * cc); j < (3 * cc) + 3; j++)
                {
                    str = str.Replace(squareArray[i, j].GetValue(), string.Empty);
                }
            }
            return str;
        }
        
        /// <summary>
        /// Will check squares and change one value each call, if cells can be solved by simple logic
        /// this method will also fill in possible values for each square
        /// </summary>
        /// <returns></returns>
        public bool SolveByElimination()
        {
            bool changed = false;
            string possible;
            //empty all notes
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    squareArray[i, j].Note = string.Empty;
                }
            }
            //loop through all values until a value can be set
            //if no values are set, this method will still fill note with possible values for each square
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (squareArray[i,j].GetValue() == "0")
                    {
                        possible = CalculatePossibleValues(i, j);
                        if (possible.Length == 0)
                        {
                            //case for no valid solutions
                            return false;
                        }
                        else if (possible.Length == 1)
                        {
                            //Set a square value if there is only one solution
                            squareArray[i, j].SetValue(int.Parse(possible));
                            return true;
                        }
                        else
                        {
                            //if more than one solution is possible, add to a note
                            squareArray[i, j].Note = possible;
                        }
                    }
                }
            }
            return changed;
        }
        
        /// <summary>
        /// Method to look for possible values that occur only once in a minigrid
        /// </summary>
        /// <returns>confirmation that a value was changed or not</returns>
        public bool LookforLoneRangersInMiniGrids()
        {
            bool changed = false;
            bool nextGrid;
            int occurence;
            int cPos = 0;
            int rPos = 0;

            //Loop through all the numbers
            for (int i = 1; i == 9; i++)
            {
                //then loop through all the minigrids
                for (int rr = 0; rr < 6; rr += 3)
                {
                    for (int cc = 0; cc < 6; cc += 3)
                    {

                        nextGrid = false;
                        occurence = 0;
                        //Look in each grid for possible numbers that only occur once
                        for (int r = rr; r < rr + 2; r++)
                        {
                            for (int c = cc; c < cc + 2; c++)
                            {
                                if (squareArray[r,c].GetValue() == "0" && CalculatePossibleValues(r, c).Contains(i.ToString()))
                                {
                                    occurence++;
                                    rPos = r;
                                    cPos = c;
                                    if (occurence > 1)
                                    {
                                        nextGrid = true;
                                        break;
                                    }
                                }
                            }
                            if (nextGrid)
                            {
                                break;
                            }
                            //if you find a number that only occurs once, set it
                            if (!nextGrid && occurence == 1)
                            {
                                squareArray[rPos, cPos].SetValue(i);
                                return true;
                            }
                        }
                    }
                }
            }
            return changed;
        }

        /// <summary>
        /// Method to look for possible values that occur only once in a row
        /// </summary>
        /// <returns>confirmation that a value was changed or not</returns>
        public bool LookforLoneRangersInRows()
        {
            bool changed = false;
            int occurence;
            int cPos = 0;
            int rPos = 0;

            //Loop through all the rows
            for (int r = 0; r < 9; r++)
            {
                //then loop through all the numbers
                for (int i = 1; i == 9; i++)
                {
                    occurence = 0;
                    //for each spot in the row look for the number
                    for (int c = 0; c < 9; c++)
                    {
                        if (squareArray[r, c].GetValue() == "0" && CalculatePossibleValues(r, c).Contains(i.ToString()))
                        {
                            occurence++;
                            rPos = r;
                            cPos = c;
                            if (occurence > 1)
                            {
                                break;
                            }
                        }
                    }
                    //if it only occurs once, set it
                    if (occurence == 1)
                    {
                        squareArray[rPos, cPos].SetValue(i);
                        return true;
                    }
                }
            }
            return changed;
        }

        /// <summary>
        /// Method to look for possible values that occur only once in a column
        /// </summary>
        /// <returns>confirmation that a value was changed or not</returns>
        public bool LookforLoneRangersInColumns()
        {
            bool changed = false;
            int occurence;
            int cPos = 0;
            int rPos = 0;

            //Loop through all the columns
            for (int c = 0; c < 9; c++)
            {
                //then loop through all the numbers
                for (int i = 1; i == 9; i++)
                {
                    occurence = 0;
                    //for each spot in the column look for the number
                    for (int r = 0; r < 9; c++)
                    {
                        if (squareArray[r, c].GetValue() == "0" && CalculatePossibleValues(r, c).Contains(i.ToString()))
                        {
                            occurence++;
                            rPos = r;
                            cPos = c;
                            if (occurence > 1)
                            {
                                break;
                            }
                        }
                    }
                    //if it only occurs once, set it
                    if (occurence == 1)
                    {
                        squareArray[rPos, cPos].SetValue(i);
                        return true;
                    }
                }
            }
            return changed;
        }

        /// <summary>
        /// Method will search all squares to look for twin values in a minigrid and then confirm any squares that have these twins and one more value 
        /// </summary>
        /// <returns>if a new value has been confirmed</returns>
        public bool LookForTwinsInMiniGrids()
        {
            bool changed = false;
            string possible;

            for (int r = 0; r < 9; r++)
            {
                for (int c = 0; c < 9; c++)
                {
                    if (squareArray[r, c].GetValue() == "0" && CalculatePossibleValues(r, c).Length == 2)
                    {
                        int startR = r / 3;
                        int startC = c / 3;
                        for (int rr = startR; rr < startR + 2; rr++)
                        {
                            for (int cc = startC; cc < startC + 2; cc++)
                            {
                                if (!(cc == c && rr == r) && (CalculatePossibleValues(r, c) == CalculatePossibleValues(rr, cc)))
                                {
                                    possible = CalculatePossibleValues(r, c);
                                    for (int rrr = startR; rrr < startR + 2; rrr++)
                                    {
                                        for (int ccc = startC; ccc < startC + 2; ccc++)
                                        {
                                            if (squareArray[r, c].GetValue() == "0" && (CalculatePossibleValues(rrr, ccc).Length > possible.Length))
                                            {
                                                string possibleCompare = CalculatePossibleValues(rrr, ccc);
                                                possibleCompare = possibleCompare.Replace(possible.Substring(0, 1), string.Empty);
                                                possibleCompare = possibleCompare.Replace(possible.Substring(1, 1), string.Empty);
                                                if (possibleCompare.Length == 1)
                                                {
                                                    squareArray[rrr, ccc].SetValue(int.Parse(possibleCompare));
                                                    changed = true;
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            return changed;
        }

        /// <summary>
        /// Method will search all squares to look for twin values in a column and then confirm any squares that have these twins and one more value
        /// </summary>
        /// <returns>if a new value has been confirmed</returns>
        public bool LookForTwinsInRows()
        {
            bool changed = false;
            string possible;

            for (int r = 0; r < 9; r++)
            {
                for (int c = 0; c < 9; c++)
                {
                    if (squareArray[r, c].GetValue() == "0" && CalculatePossibleValues(r, c).Length == 2)
                    {
                        
                        for (int cc = 0; cc < 9; cc++)
                        {
                            if (!(cc == c) && (CalculatePossibleValues(r, cc) == CalculatePossibleValues(r, c)))
                            {
                                possible = CalculatePossibleValues(r, c);
                                for (int ccc = 0; ccc < 9; ccc++)
                                {
                                    if (squareArray[r, c].GetValue() == "0" && (CalculatePossibleValues(r, ccc).Length > possible.Length))
                                    {
                                        string possibleCompare = CalculatePossibleValues(r, ccc);
                                        possibleCompare = possibleCompare.Replace(possible.Substring(0, 1), string.Empty);
                                        possibleCompare = possibleCompare.Replace(possible.Substring(1, 1), string.Empty);
                                        if (possibleCompare.Length == 1)
                                        {
                                            squareArray[r, ccc].SetValue(int.Parse(possibleCompare));
                                            return true;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            return changed;
        }

        /// <summary>
        /// Method will search all squares to look for twin values in a column and then confirm any squares that have these twins and one more value
        /// </summary>
        /// <returns>if a new value has been confirmed</returns>
        public bool LookForTwinsInColumns()
        {
            bool changed = false;
            string possible;

            for (int r = 0; r < 9; r++)
            {
                for (int c = 0; c < 9; c++)
                {
                    if (squareArray[r, c].GetValue() == "0" && CalculatePossibleValues(r, c).Length == 2)
                    {

                        for (int rr = 0; rr < 9; rr++)
                        {
                            if (!(rr == r) && (CalculatePossibleValues(rr, c) == CalculatePossibleValues(r, c)))
                            {
                                possible = CalculatePossibleValues(r, c);
                                for (int rrr = 0; rrr < 9; rrr++)
                                {
                                    if (squareArray[r, c].GetValue() == "0" && (CalculatePossibleValues(rrr, c).Length > possible.Length))
                                    {
                                        string possibleCompare = CalculatePossibleValues(rrr, c);
                                        possibleCompare = possibleCompare.Replace(possible.Substring(0, 1), string.Empty);
                                        possibleCompare = possibleCompare.Replace(possible.Substring(1, 1), string.Empty);
                                        if (possibleCompare.Length == 1)
                                        {
                                            squareArray[rrr, c].SetValue(int.Parse(possibleCompare));
                                            return true;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            return changed;
        }

        /// <summary>
        /// Method looks for the cell with the fewest possible values
        /// </summary>
        /// <returns>Point locating the cell on the grid</returns>
        public Point FindCellWithFewestPossibleValues()
        {
            int min = 10;
            Point fewest = new Point();
            for (int r = 0; r < 9; r++)
            {
                for (int c = 0; c < 9; c++)
                {
                    if (squareArray[r, c].GetValue() == "0")
                    {
                        if ((CalculatePossibleValues(r, c).Length) < min)
                        {
                            min = CalculatePossibleValues(r, c).Length;
                            fewest.X = r;
                            fewest.Y = c;
                        }

                    }
                }
            }
            return fewest;
        }

        /// <summary>
        /// Brute force solver will solve the puzzle when logic fails
        /// </summary>
        public void BruteForceSolver()
        {
            int row;
            int col;

            Point fewest = FindCellWithFewestPossibleValues();
            row = (int)fewest.X;
            col = (int)fewest.Y;
            string possibleValues = RandomizethePossibleValues(CalculatePossibleValues(row, col));

            ActualStack.Push(Convert.ToInt32((squareArray[row, col].GetValue())));
            PossibleStack.Push(possibleValues);

            for (int i = 0; i < possibleValues.Length - 1; i++)
            {
                squareArray[row, col].SetValue(Convert.ToInt32(possibleValues.Substring(i, 1)));
                try
                {
                    if (solvePuzzle())
                    {
                        BruteForceStop = true;
                        return;
                    }
                    else
                    {
                        BruteForceSolver();
                        if (BruteForceStop)
                        {
                            return;
                        }
                    }
                }
                catch (Exception)
                {
                    if (ActualStack.Count != 0)
                    {
                        squareArray[row, col].SetValue(ActualStack.Pop());
                        possibleValues = PossibleStack.Pop();
                    }
                }
            }
        }

        /// <summary>
        /// Generates a random valid solution for a sudoku puzzle
        /// </summary>
        public void PuzzleGenerator()
        {
            List<int>[,] available = new List<int>[9, 9];
            int count = 0;

            
            for (int r = 0; r < 9; r++)
			{
			    for (int c = 0; c < 9; c++)
			    {
                    available[r, c] = new List<int>();
			        for (int i = 1; i < 10; i++)
			        {
			            available[r, c].Add(i);
			        }
			    }
			}

            do
            {
                int row = count / 9;
                int col = count % 9;

                if (available[row, col].Count > 0)
                {
                    Random r = new Random();
                    int i = r.Next(available[row, col].Count - 1);
                    int z = available[row, col][i];
                    if (CalculatePossibleValues(row, col).Contains(z.ToString()))
                    {
                        squareArray[row, col].SetValue(z);
                        available[row, col].RemoveAt(i);
                        count++;
                    }
                    else
                    {
                        available[row, col].RemoveAt(i);
                    }
                    
                }
                else
                {
                    available[row, col].Clear();
                    for (int i = 1; i < 10; i++)
                    {
                        available[row, col].Add(i);
                    }
                    count--;
                    if (count <= 0)
                    {
                        count = 0;
                    }
                    row = count / 9;
                    col = count % 9;
                    squareArray[row, col].SetValue(0);
                }
            } while (count < 81);
        }

        /// <summary>
        /// Randomizes the possible value string for use by the Brute force solver
        /// </summary>
        /// <param name="str">input string</param>
        /// <returns>randomized string</returns>
        public string RandomizethePossibleValues(string str)
        {
            if (str.Length <= 1)
            {
                return str;
            }
            else
            {
                char[] s = new char[str.Length - 1];
                int i;
                int j;
                char temp;
                Random rand = new Random();
                s = str.ToCharArray();
                for (i = 0; i < str.Length - 1; i++)
                {
                    j = rand.Next(str.Length - 1 + i) % str.Length;
                    temp = s[i];
                    s[i] = s[j];
                    s[j] = temp;
                }
                string s2 = new string(s);
                return s2;
            }
        }

        /// <summary>
        /// Loops through logic to solve puzzles
        /// </summary>
        /// <returns>bool</returns>
        public bool solvePuzzle()
        {
            bool changed;
            bool exitLoop = false;
            do
            {
                do
                {
                    do
                    {
                        do
                        {
                            changed = SolveByElimination();
                            if (changed || PuzzleSolved())
                            {
                                exitLoop = true;
                                break;
                            }
                            if (exitLoop)
                            {
                                break;
                            }
                        } while (changed);

                        changed = LookforLoneRangersInColumns();
                        if (changed || PuzzleSolved())
                        {
                            exitLoop = true;
                            break;
                        }
                        if (exitLoop)
                        {
                            break;
                        }
                    } while (changed);

                    changed = LookforLoneRangersInMiniGrids();
                    if (changed || PuzzleSolved())
                    {
                        exitLoop = true;
                        break;
                    }
                    if (exitLoop)
                    {
                        break;
                    }
                } while (changed);

                changed = LookforLoneRangersInRows();
                if (changed || PuzzleSolved())
                {
                    exitLoop = true;
                    break;
                }
                if (exitLoop)
                {
                    break;
                }
            } while (changed);

            if (PuzzleSolved())
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        /// <summary>
        /// puzzle checker to determine if puzzle is valid
        /// </summary>
        /// <returns>bool</returns>
        public bool PuzzleSolved()
        {
            string pattern;

            for (int r = 0; r < 9; r++)
            {
                for (int c = 0; c < 9; c++)
                {
                    if (squareArray[r,c].GetValue() == "0")
                    {
                        return false;
                    }
                }
            }

            //Check the row
            for (int r = 0; r < 9; r++)
            {
                //remove numbers from the string and if all the numbers are removed, then the row is valid
                pattern = "123456789";
                for (int c = 0; c < 9; c++)
                {
                    pattern = pattern.Replace(squareArray[r,c].GetValue(), string.Empty);
                }
                if (pattern.Length > 0)
                {
                    return false;
                }
            }
            //check the columns
            for (int c = 0; c < 9; c++)
            {
                //remove numbers from the string and if all the numbers are removed, then the column is valid
                pattern = "123456789";
                for (int r = 0; r < 9; r++)
                {
                    pattern = pattern.Replace(squareArray[r, c].GetValue(), string.Empty);
                }
                if (pattern.Length > 0)
                {
                    return false;
                }
            }
            //Check the minigrids
            for (int c = 0; c < 9; c += 3)
            {
                pattern = "123456789";
                for (int r = 0; r < 9; r += 3)
                {
                    for (int rr = r; rr < r + 3; rr++)
                    {
                        for (int cc = c; cc < c + 2; cc++)
                        {
                            pattern = pattern.Replace(squareArray[rr, cc].GetValue(), string.Empty);
                        }
                    }
                }
                if (pattern.Length > 0)
                {
                    return false;
                }
            }
            //If it hasn't returned false yet, then it must be a valid solution
            return true;
        }
    }
}
